package com.hdu.hot100.backTrack;

import java.util.ArrayList;
import java.util.List;

public class lc51 {
    class Solution {

        char[][] board;

        List<List<String>> ans = new ArrayList<>();
        public List<List<String>> solveNQueens(int n)
        {
            board = createBoard(n);
            f(n, 0);
            return ans;
        }

        void f(int n, int curRow)
        {
            if (curRow == n)
            {
                recordBoard();
                return;
            }
            for (int curCol = 0; curCol < n; curCol++)
            {
                if (!canPutQ(curRow, curCol))
                {
                    continue;
                }
                board[curRow][curCol] = 'Q';
                f(n, curRow + 1);
                board[curRow][curCol] = '.';
            }
        }

        boolean canPutQ(int row, int col)
        {
            for (int i = 0; i < row; i++)
            {
                if (board[i][col] == 'Q')
                {
                    return false;
                }
            }
            for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--)
            {
                if (board[i][j] == 'Q')
                {
                    return false;
                }
            }

            for (int i = row - 1, j = col + 1; i >= 0 && j < board[0].length; i--, j++)
            {
                if (board[i][j] == 'Q')
                {
                    return false;
                }
            }

            return true;
        }

        void recordBoard()
        {
            List<String> path = new ArrayList<>();
            for (int i = 0; i < board.length; i++)
            {
                StringBuilder sb = new StringBuilder();
                for (int j = 0; j < board[0].length; j++)
                {
                    sb.append(board[i][j]);
                }
                path.add(sb.toString());
            }
            ans.add(path);
        }

        char[][] createBoard(int n)
        {
            char[][] board = new char[n][n];
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    board[i][j] = '.';
                }
            }
            return board;
        }
    }
}
